\documentclass{article}
\usepackage{xeCJK}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[hidelinks]{hyperref}
\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}

\title{离散数学作业}
\author{2020141460280张家帅}
\begin{document}
\maketitle
非常非常抱歉，我真的太拖延了，而且因为时间久远，我已经分不清第几周了 Orz

我把作业放到一起，目录加上超链接了，希望不要给您造成太大的麻烦，感谢批改！
\tableofcontents
\newpage
\section*{习题五}
\addcontentsline{toc}{section}{习题五}
\subsection*{1}
\addcontentsline{toc}{subsection}{1}
证明：

1. $\forall (a,b)\in A$

\[ ab = ba\Rightarrow ((a,b),(a,b))\in R\]

所以自反性成立

2. $\forall (a,b),(c,d)\in A$

\begin{align*}
	              & ((a,b),(c,d))\in R \\
	\Rightarrow{} & ad = bc            \\
	\Rightarrow{} & da = cb            \\
	\Rightarrow{} & ((c,d),(a,b))\in R
\end{align*}

所以对称性成立

3. $\forall (a,b),(c,d),(e,f)\in A$
\begin{align*}
	              & ((a,b),(c,d))\in R\wedge ((c,d),(e,f))\in R        \\
	\Rightarrow{} & ad = bc\wedge cf = de                              \\
	\Rightarrow{} & af = a\cdot \frac{de}{c} = ae \cdot \frac{d}{c}=be \\
	\Rightarrow{} & ((a,b),(e,f))\in R
\end{align*}

所以传递性成立

因此，$R$是$A$上的等价关系得证
\subsection*{3}
\addcontentsline{toc}{subsection}{3}
因为自反性：$(1,1),(2,2),(3,3),(4,4)\in R$\\
因为对称性和传递性：$(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\in R$

因此：
\[R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\}\]

\subsection*{6}
\addcontentsline{toc}{subsection}{6}
要证明$R$是$A$上的等价关系，只要证明$R$满足自反性：

\begin{align*}
	              & \forall x\in A, \exists y\in A, xRy  \mbox  {(已知)} \\
	\Rightarrow{} & yRx                                  \mbox{(对称性)} \\
	\Rightarrow{} & xRx                                  \mbox{(传递性)} \\
\end{align*}



\subsection*{8}
\addcontentsline{toc}{subsection}{8}

由题得：
\[A=\{1,2,3,6,9,18,27,54\}\]
所以$<A,\mid>$对应的$Hasse$图为
\begin{center}
	\begin{tikzpicture}
		[
			dot/.style={circle,draw,inner sep=1.5pt},
		]
		\node[dot](1) at (0,0) {};
		\node[dot](2) at (-1,1) {}
		edge[-] (1);
		\node[dot](3) at (1,1) {}
		edge[-] (1);
		\node[dot](6) at (0,2) {}
		edge[-] (2)
		edge[-] (3);
		\node[dot](9) at (2,2) {}
		edge[-] (3);
		\node[dot](18) at (1,3) {}
		edge[-] (6)
		edge[-] (9);
		\node[dot](27) at (3,3) {}
		edge[-] (9);
		\node[dot](54) at (2,4) {}
		edge[-] (18)
		edge[-] (27);

		\node[below] at (1.south) {1};
		\node[left] at (2.west) {2};
		\node[below] at (3.east) {3};
		\node[above] at (6.west) {6};
		\node[below] at (9.east) {9};
		\node[above] at (18.west) {18};
		\node[right] at (27.east) {27};
		\node[above] at (54.north) {54};
	\end{tikzpicture}
\end{center}

\subsection*{15}
\addcontentsline{toc}{subsection}{15}
由题得：
\begin{align*}
	2^A=\left\{\varnothing,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\right. \\
	\left.\{c,d\},\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\},\{a,b,c,d\}\right\}
\end{align*}

定义的全序为：
\begin{align*}
	\varnothing\preccurlyeq\{a\}\preccurlyeq\{b\}\preccurlyeq\{c\}\preccurlyeq\{d\}\preccurlyeq\{a,b\}\preccurlyeq\{a,c\}
	\preccurlyeq\{b,c\}\preccurlyeq\{a,d\}\preccurlyeq\{b,d\} \\
	\preccurlyeq\{c,d\}\preccurlyeq\{a,b,c\}\preccurlyeq\{a,b,d\}\preccurlyeq\{a,c,d\}\preccurlyeq\{b,c,d\}\preccurlyeq\{a,b,c,d\}
\end{align*}
\section*{习题六}
\addcontentsline{toc}{section}{习题六}

\subsection*{1}
\addcontentsline{toc}{subsection}{1}
\subsubsection*{(1)}
\addcontentsline{toc}{subsubsection}{(1)}
处处有定义，是$A$到$B$的全函数
\subsubsection*{(2)}
\addcontentsline{toc}{subsubsection}{(2)}
自变量重复，不满足函数序偶中第一个元素互不相同的规则，所以不是函数
\subsubsection*{(3)}
\addcontentsline{toc}{subsubsection}{(3)}
处处有定义，是$A$到$B$的全函数

\subsection*{2}
\addcontentsline{toc}{subsection}{2}
\subsubsection*{(2)}
\addcontentsline{toc}{subsubsection}{(2)}
是部分函数，因为0没有因子，函数不是处处有定义

\subsubsection*{(3)}
\addcontentsline{toc}{subsubsection}{(3)}
$S_1$取$\{a\}$时，$S_2$有多种取值，因此不是函数，更不是全函数

\subsection*{8}
\addcontentsline{toc}{subsection}{8}
\subsubsection*{(1)}
\addcontentsline{toc}{subsubsection}{(1)}
由题意得，$f$是集合$X$到自身的映射，且$f$为单射，由单射定义可知，一个因变量只对应一个自变量，由函数定义可知，一个自变量只对应
一个因变量，因此自变量和因变量一一对应，又因为是在$X$上的变换，得到自变量因变量个数相同，因此为满射，所以为双射
\subsubsection*{(2)}
\addcontentsline{toc}{subsubsection}{(2)}
如果每一个因变量都有自变量与之对应，且因变量自变量数量相同，那么一定所有的自变量都和因变量一一对应，所以为双射

\subsection*{9}
\addcontentsline{toc}{subsection}{9}
单射：\\
如果$f(x_1)=f(x_2)$，那么$f^2(x_1)=f^2(x_2)$，得到$x_1=x_2$，因此$f$为单射\\
满射：\\
由题意得，$f$是集合$X$到自身的映射，且$f$为单射，由单射定义可知，一个因变量只对应一个自变量，由函数定义可知，一个自变量只对应
一个因变量，因此自变量和因变量一一对应，又因为是在$X$上的变换，得到自变量因变量个数相同，因此为满射，所以为双射

\subsection*{12}
\addcontentsline{toc}{subsection}{12}
\begin{align*}
	(f\circ g)(x) & =f(g(x))    \\
	              & =f(x^2+x-1) \\
	              & =2x^2+2x-2
\end{align*}
\begin{align*}
	(g\circ f\circ h)(x) & =g(f(h(x)))  \\
	                     & =g(f(x-2))   \\
	                     & =g(2x-4)     \\
	                     & =4x^2-14x+11
\end{align*}
\begin{align*}
	(h\circ h\circ g)(x) & =h(h(g(x)))    \\
	                     & =h(h(x^2+x-1)) \\
	                     & =h(x^2+x-3)    \\
	                     & =x^2+x-5
\end{align*}

\subsection*{14}
\addcontentsline{toc}{subsection}{14}
$(f\circ g)(x)=4x^2-4x+5$\\
如果$y$为5，那么$x$可能为0或1，不是单射；对于$y\leqslant 0$，没有$x$与之对应，所以为不是满射；更不是双射\\
$(g\circ f)(x)=2x^2+3$
同上，不是单射也不是满射更不是双射
\subsection*{15}
\addcontentsline{toc}{subsection}{15}
\subsubsection*{(1)}
\addcontentsline{toc}{subsubsection}{(1)}
由题得：
\begin{align*}
	x_1\neq x_2 & \Rightarrow{} g(f(x_1))\neq g(f(x_2)) \\
	            & \Rightarrow{}  f(x_1)\neq f(x_2)
\end{align*}
所以$f$为单射
\subsubsection*{(2)}
\addcontentsline{toc}{subsubsection}{(2)}
由题得：
\begin{align*}
	\forall z\in \mathop{ran}g\circ f,\exists x\in \mathop{dom}g\circ f \\
	\Rightarrow{} \forall z\in \mathop{ran}g,\exists f(x)\in \mathop{dom}g
\end{align*}
所以$g$为满射
\subsubsection*{(3)}
\addcontentsline{toc}{subsubsection}{(3)}
由题，$g\circ f$为双射，即$g\circ f$既为单射又为满射，由前两道题，$g$为满射，$f$为单射

\end{document}